{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cyclically Rotating a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rotateGrid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #循环轮转矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的整数矩阵 <code>grid</code>​​​ ，其中 <code>m</code> 和 <code>n</code> 都是 <strong>偶数</strong> ；另给你一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>矩阵由若干层组成，如下图所示，每种颜色代表一层：</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/10/ringofgrid.png\" style=\"width: 231px; height: 258px;\"></p>\n",
    "\n",
    "<p>矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 <strong>逆时针 </strong>方向的相邻元素。轮转示例如下：</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/22/explanation_grid.jpg\" style=\"width: 500px; height: 268px;\">\n",
    "<p>返回执行 <code>k</code> 次循环轮转操作后的矩阵。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/19/rod2.png\" style=\"width: 421px; height: 191px;\">\n",
    "<pre><strong>输入：</strong>grid = [[40,10],[30,20]], k = 1\n",
    "<strong>输出：</strong>[[10,20],[40,30]]\n",
    "<strong>解释：</strong>上图展示了矩阵在执行循环轮转操作时每一步的状态。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/10/ringofgrid5.png\" style=\"width: 231px; height: 262px;\"></strong> <strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/10/ringofgrid6.png\" style=\"width: 231px; height: 262px;\"></strong> <strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/06/10/ringofgrid7.png\" style=\"width: 231px; height: 262px;\"></strong>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2\n",
    "<strong>输出：</strong>[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]\n",
    "<strong>解释：</strong>上图展示了矩阵在执行循环轮转操作时每一步的状态。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>2 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>m</code> 和 <code>n</code> 都是 <strong>偶数</strong></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;=<sup> </sup>5000</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cyclically-rotating-a-grid](https://leetcode.cn/problems/cyclically-rotating-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cyclically-rotating-a-grid](https://leetcode.cn/problems/cyclically-rotating-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[40,10],[30,20]]\\n1', '[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        left_m = 0\n",
    "        right_m = m-1\n",
    "        left_n = 0\n",
    "        right_n = n-1\n",
    "        for _ in range(min(m//2,n//2)):\n",
    "            num_sum = (right_m+1-left_m)*2+(right_n+1-left_n)*2-4\n",
    "            num_k = k\n",
    "            num_k = num_k%num_sum\n",
    "            pos = []\n",
    "            val = []\n",
    "            for i in range(right_n,left_n,-1):\n",
    "                pos.append([left_m,i])\n",
    "                val.append(grid[left_m][i])\n",
    "            for i in range(left_m,right_m):\n",
    "                pos.append([i,left_n])\n",
    "                val.append(grid[i][left_n])\n",
    "            for i in range(left_n,right_n):\n",
    "                pos.append([right_m,i])\n",
    "                val.append(grid[right_m][i])\n",
    "            for i in range(right_m,left_m,-1):\n",
    "                pos.append([i,right_n])\n",
    "                val.append(grid[i][right_n])\n",
    "            for i in range(num_sum):\n",
    "                target = (i+num_k)%(num_sum)\n",
    "                grid[pos[target][0]][pos[target][1]] = val[i]\n",
    "            left_m+=1\n",
    "            right_m-=1\n",
    "            left_n+=1\n",
    "            right_n-=1\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        layer = min(m // 2, n // 2)\n",
    "        for a in range(layer):\n",
    "            val = []\n",
    "            for i in range(a, m - a - 1):\n",
    "                val.append((i, a, grid[i][a]))\n",
    "            for j in range(a, n - a - 1):\n",
    "                val.append((m - a - 1, j, grid[m - a - 1][j]))\n",
    "            for i in range(m - a - 1, a, -1):\n",
    "                val.append((i, n - a - 1, grid[i][n - a - 1]))\n",
    "            for j in range(n - a - 1, a, -1):\n",
    "                val.append((a, j, grid[a][j]))\n",
    "            tot = len(val)\n",
    "            # print(val)\n",
    "            kk = k % tot\n",
    "            for i in range(tot):\n",
    "                idx = (i + tot - kk) % tot\n",
    "                grid[val[i][0]][val[i][1]] = val[idx][2]\n",
    "            # print(grid)\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        Row, Col = len(grid), len(grid[0])\n",
    "            \n",
    "        Len = min(Row, Col) // 2       \n",
    "        for L in range(0, Len):      \n",
    "            loopLen = 2 * ((Row - 2*L) + (Col - 2*L)) - 4\n",
    "            Left = L\n",
    "            Right = Col - 1 - L\n",
    "            Up = L\n",
    "            Down = Row - 1 - L\n",
    "\n",
    "            offset = k % loopLen\n",
    "            a = []\n",
    "            \n",
    "            #左竖\n",
    "            c = Left\n",
    "            for r in range(Up, Down):\n",
    "                a.append(grid[r][c])\n",
    "            #下\n",
    "            r = Down\n",
    "            for c in range(Left, Right):\n",
    "                a.append(grid[r][c])\n",
    "            #右\n",
    "            c = Right\n",
    "            for r in range(Down, Up, -1):\n",
    "                a.append(grid[r][c])\n",
    "            #上\n",
    "            r = Up\n",
    "            for c in range(Right, Left, -1):\n",
    "                a.append(grid[r][c])\n",
    "\n",
    "            ai = (loopLen - offset) % loopLen       #万一offset = 0 必须 %loopLen\n",
    "\n",
    "            #左竖\n",
    "            c = Left\n",
    "            for r in range(Up, Down):\n",
    "                grid[r][c] = a[ai]\n",
    "                ai = (ai + 1) % loopLen\n",
    "            #下\n",
    "            r = Down\n",
    "            for c in range(Left, Right):\n",
    "                grid[r][c] = a[ai]\n",
    "                ai = (ai + 1) % loopLen\n",
    "            #右\n",
    "            c = Right\n",
    "            for r in range(Down, Up, -1):\n",
    "                grid[r][c] = a[ai]\n",
    "                ai = (ai + 1) % loopLen\n",
    "            #上\n",
    "            r = Up\n",
    "            for c in range(Right, Left, -1):\n",
    "                grid[r][c] = a[ai]\n",
    "                ai = (ai + 1) % loopLen\n",
    "                \n",
    "        return grid\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        layer_nums = min(m // 2, n // 2)\n",
    "\n",
    "        layers = []\n",
    "        for i in range(layer_nums):\n",
    "            a = grid[-i-1][i:n-i]\n",
    "            b = [grid[j][-i-1] for j  in range(m-i-1, i-1, -1)]\n",
    "            c = [grid[i][j] for j  in range(n-i-1, i-1, -1)]\n",
    "            d = [grid[j][i] for j  in range(i, m-i, 1)]\n",
    "            layer = a[:-1] + b[:-1] + c[:-1] + d[:-1]\n",
    "            layer = layer[-k % len(layer):] + layer[0:-k % len(layer)]\n",
    "            layers.append(layer)\n",
    "\n",
    "        for i in range(layer_nums):\n",
    "            nums = len(layers[i])\n",
    "            grid[-i-1][i:-i-1] = layers[i][:len(grid[-i-1][i:-i-1])]\n",
    "            idx = len(grid[-i-1][i:-i-1])\n",
    "            for j  in range(m-i-1, i, -1):\n",
    "                grid[j][-i-1] = layers[i][idx]\n",
    "                idx += 1\n",
    "            for j  in range(n-i-1, i, -1):\n",
    "                grid[i][j] = layers[i][idx]\n",
    "                idx += 1\n",
    "            for j  in range(i, m-i-1, 1):\n",
    "                grid[j][i] = layers[i][idx]\n",
    "                idx += 1\n",
    "            \n",
    "        return grid\n",
    "        \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        nlayer = min(m // 2, n // 2)   # 层数\n",
    "        # 从左上角起逆时针枚举每一层\n",
    "        for layer in range(nlayer):\n",
    "            r = []   # 每个元素的行下标\n",
    "            c = []   # 每个元素的列下标\n",
    "            val = []   # 每个元素的数值\n",
    "            for i in range(layer, m - layer - 1):   # 左 \n",
    "                r.append(i)\n",
    "                c.append(layer)\n",
    "                val.append(grid[i][layer])\n",
    "            for j in range(layer, n - layer - 1):   # 下\n",
    "                r.append(m - layer - 1)\n",
    "                c.append(j)\n",
    "                val.append(grid[m-layer-1][j])\n",
    "            for i in range(m - layer - 1, layer, -1):   # 右\n",
    "                r.append(i)\n",
    "                c.append(n - layer - 1)\n",
    "                val.append(grid[i][n-layer-1])\n",
    "            for j in range(n - layer - 1, layer, -1):   # 上\n",
    "                r.append(layer)\n",
    "                c.append(j)\n",
    "                val.append(grid[layer][j])\n",
    "            total = len(val)   # 每一层的元素总数\n",
    "            kk = k % total   # 等效轮转次数\n",
    "            # 找到每个下标对应的轮转后的取值\n",
    "            for i in range(total):\n",
    "                idx = (i + total - kk) % total   # 轮转后取值对应的下标\n",
    "                grid[r[i]][c[i]] = val[idx]\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        nlayers = min(m//2, n//2)\n",
    "\n",
    "        for layer in range(nlayers):\n",
    "            r = []\n",
    "            l = []\n",
    "            val = []\n",
    "            for i in range(layer, m-1-layer):\n",
    "                r.append(i)\n",
    "                l.append(layer)\n",
    "                val.append(grid[i][layer])\n",
    "            for i in range(layer, n-1-layer):\n",
    "                r.append(m-1-layer)\n",
    "                l.append(i)\n",
    "                val.append(grid[m-1-layer][i])\n",
    "            for i in range(m-1-layer, layer,-1):\n",
    "                r.append(i)\n",
    "                l.append(n-1-layer)\n",
    "                val.append(grid[i][n-1-layer])\n",
    "            for i in range(n-1-layer,layer,-1):\n",
    "                r.append(layer)\n",
    "                l.append(i)\n",
    "                val.append(grid[layer][i])\n",
    "            \n",
    "            length = len(val)\n",
    "            for i in range(length):\n",
    "                grid[r[i]][l[i]] = val[(i-k)%length]\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "\n",
    "        layer_cnt = min(m, n) // 2\n",
    "        for i in range(layer_cnt):\n",
    "            x1,y1=i,i\n",
    "            height=m-2*i\n",
    "            width=n-2*i\n",
    "            size=2*height+2*width -4\n",
    "            kk=k %size\n",
    "            if kk==0:\n",
    "                continue\n",
    "            pos=[]\n",
    "            #pos.append([x1,y1])\n",
    "            while y1+1<n-i:\n",
    "                pos.append([x1,y1])\n",
    "                y1=y1+1\n",
    "            while x1+1<m-i:\n",
    "                pos.append([x1,y1])\n",
    "                x1=x1+1\n",
    "            while y1-1>=i:\n",
    "                pos.append([x1,y1])\n",
    "                y1=y1-1\n",
    "            while x1-1>=i:\n",
    "                pos.append([x1,y1])\n",
    "                x1=x1-1\n",
    "            lst=[0]*size\n",
    "\n",
    "            for i in range(size):\n",
    "                src=(i+kk)%size\n",
    "                x2,y2=pos[src]\n",
    "                lst[i]=grid[x2][y2]\n",
    "\n",
    "            for i in range(size):\n",
    "                x3,y3=pos[i]\n",
    "                grid[x3][y3]=lst[i]\n",
    "\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def rotate(x,y,m,n):\n",
    "            t = k % (2*m+2*n-4)\n",
    "            tmp = []\n",
    "            for i in range(x,x+m-1):\n",
    "                tmp.append(grid[i][y])\n",
    "            for j in range(y,y+n-1):\n",
    "                tmp.append(grid[x+m-1][j])\n",
    "            for i in range(x+m-1,x,-1):\n",
    "                tmp.append(grid[i][y+n-1])\n",
    "            for j in range(y+n-1,y,-1):\n",
    "                tmp.append(grid[x][j])\n",
    "            tmp = tmp[-t:] +tmp[:-t]\n",
    "            idx = 0\n",
    "            for i in range(x,x+m-1):\n",
    "                grid[i][y] = tmp[idx]\n",
    "                idx += 1\n",
    "            for j in range(y,y+n-1):\n",
    "                grid[x+m-1][j] = tmp[idx]\n",
    "                idx += 1\n",
    "            for i in range(x+m-1,x,-1):\n",
    "                grid[i][y+n-1] = tmp[idx]\n",
    "                idx += 1\n",
    "            for j in range(y+n-1,y,-1):\n",
    "                grid[x][j] = tmp[idx]\n",
    "                idx += 1\n",
    "            return\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        x,y = 0,0\n",
    "        while(m >= 2 and n >= 2):\n",
    "            rotate(x,y,m,n)\n",
    "            m -= 2\n",
    "            n -= 2\n",
    "            x += 1\n",
    "            y += 1\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ret = [[0] * n for _ in range(m)]\n",
    "        layer = min(m, n) // 2\n",
    "        rotate = k\n",
    "        for k in range(layer):\n",
    "            g = []\n",
    "            for i in range(k, n - k):\n",
    "                g.append((k, i))\n",
    "            for i in range(k + 1, m - k):\n",
    "                g.append((i, n - k - 1))\n",
    "            for i in range(n - k - 2, k - 1, -1):\n",
    "                g.append((m - k - 1, i))\n",
    "            for i in range(m - k - 2, k, -1):\n",
    "                g.append((i, k))\n",
    "            cnt = 2 * n + 2 * m - 4 - 8 * k\n",
    "            # print(len(g), cnt, k, n, m)\n",
    "            p = rotate % cnt\n",
    "            for i in range(cnt):\n",
    "                j = (i + p) % cnt\n",
    "                ret[g[i][0]][g[i][1]] = grid[g[j][0]][g[j][1]]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        layerLen = min(row // 2, col //2)\n",
    "        for layer in range(layerLen):\n",
    "            rowIndex, colIndex, val = [], [], []\n",
    "            for i in range(layer, row - layer - 1):\n",
    "                rowIndex.append(i)\n",
    "                colIndex.append(layer)\n",
    "                val.append(grid[i][layer])\n",
    "\n",
    "            for i in range(layer, col - layer - 1):\n",
    "                rowIndex.append(row - layer - 1)\n",
    "                colIndex.append(i)\n",
    "                val.append(grid[row - layer - 1][i])\n",
    "\n",
    "            for i in range(row - layer - 1, layer, -1):\n",
    "                rowIndex.append(i)\n",
    "                colIndex.append(col - layer - 1)\n",
    "                val.append(grid[i][col - layer - 1])\n",
    "\n",
    "            for i in range(col - layer - 1, layer, -1):\n",
    "                rowIndex.append(layer)\n",
    "                colIndex.append(i)\n",
    "                val.append(grid[layer][i])\n",
    "            offSet = k % len(val)\n",
    "            for i in range(len(val)):\n",
    "                # idx = (i + len(val) - offSet) % len(val)\n",
    "                # grid[rowIndex[i]][colIndex[i]] = val[idx]\n",
    "                placeIndex = i + offSet\n",
    "                if placeIndex >= len(val):\n",
    "                    placeIndex = placeIndex - len(val)\n",
    "                grid[rowIndex[placeIndex]][colIndex[placeIndex]] = val[i]\n",
    "        return grid\n",
    "                 \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for k0 in range(min(m, n) // 2):\n",
    "            topleft = k0, k0\n",
    "            bottomright = m - k0 - 1, n - k0 - 1\n",
    "            poses = []\n",
    "            nums = []\n",
    "            # 从左上角开始逆时针旋转\n",
    "            for i in range(topleft[0] + 1, bottomright[0] + 1):\n",
    "                poses.append((i, topleft[1]))\n",
    "                nums.append(grid[i][topleft[1]])\n",
    "            for j in range(topleft[1] + 1, bottomright[1] + 1):\n",
    "                poses.append((bottomright[0], j))\n",
    "                nums.append(grid[bottomright[0]][j])\n",
    "            for i in range(bottomright[0] - 1, topleft[0] - 1, -1):\n",
    "                poses.append((i, bottomright[1]))\n",
    "                nums.append(grid[i][bottomright[1]])\n",
    "            for j in range(bottomright[1] - 1, topleft[1] - 1, -1):\n",
    "                poses.append((topleft[0], j)) \n",
    "                nums.append(grid[topleft[0]][j])\n",
    "            gap = k % ((bottomright[0] - topleft[0] + 1 + bottomright[1] - topleft[1] + 1)*2-4)  # 一圈的长度\n",
    "            nums = nums[-gap:] + nums[:-gap]\n",
    "            for (i, j), x in zip(poses, nums):\n",
    "                grid[i][j] = x\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k1: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for k in range(min(m, n) // 2):\n",
    "            topleft = k, k\n",
    "            bottomright = m - k - 1, n - k - 1\n",
    "            poses = []\n",
    "            nums = []\n",
    "            # 从左上角开始逆时针旋转\n",
    "            for i in range(topleft[0] + 1, bottomright[0] + 1):\n",
    "                poses.append((i, topleft[1]))\n",
    "                nums.append(grid[i][topleft[1]])\n",
    "            for j in range(topleft[1] + 1, bottomright[1] + 1):\n",
    "                poses.append((bottomright[0], j))\n",
    "                nums.append(grid[bottomright[0]][j])\n",
    "            for i in range(bottomright[0] - 1, topleft[0] - 1, -1):\n",
    "                poses.append((i, bottomright[1]))\n",
    "                nums.append(grid[i][bottomright[1]])\n",
    "            for j in range(bottomright[1] - 1, topleft[1] - 1, -1):\n",
    "                poses.append((topleft[0], j)) \n",
    "                nums.append(grid[topleft[0]][j])\n",
    "            k0 = k1 % ((bottomright[0] - topleft[0] + 1 + bottomright[1] - topleft[1] + 1)*2-4)  # 一圈的长度\n",
    "            print(nums, k0)\n",
    "            nums = nums[-k0:] + nums[:-k0]\n",
    "            print(nums)\n",
    "            for (i, j), x in zip(poses, nums):\n",
    "                grid[i][j] = x\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def rotate(x,y,m,n):\n",
    "            t = k % (2*m+2*n-4)\n",
    "            tmp = []\n",
    "            for i in range(x,x+m-1):\n",
    "                tmp.append(grid[i][y])\n",
    "            for j in range(y,y+n-1):\n",
    "                tmp.append(grid[x+m-1][j])\n",
    "            for i in range(x+m-1,x,-1):\n",
    "                tmp.append(grid[i][y+n-1])\n",
    "            for j in range(y+n-1,y,-1):\n",
    "                tmp.append(grid[x][j])\n",
    "            tmp = tmp[-t:] +tmp[:-t]\n",
    "            idx = 0\n",
    "            for i in range(x,x+m-1):\n",
    "                grid[i][y] = tmp[idx]\n",
    "                idx += 1\n",
    "            for j in range(y,y+n-1):\n",
    "                grid[x+m-1][j] = tmp[idx]\n",
    "                idx += 1\n",
    "            for i in range(x+m-1,x,-1):\n",
    "                grid[i][y+n-1] = tmp[idx]\n",
    "                idx += 1\n",
    "            for j in range(y+n-1,y,-1):\n",
    "                grid[x][j] = tmp[idx]\n",
    "                idx += 1\n",
    "            return\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        x,y = 0,0\n",
    "        while(m >= 2 and n >= 2):\n",
    "            rotate(x,y,m,n)\n",
    "            m -= 2\n",
    "            n -= 2\n",
    "            x += 1\n",
    "            y += 1\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        nlayer = min(m // 2, n // 2)   # 层数\n",
    "        # 从左上角起逆时针枚举每一层\n",
    "        for layer in range(nlayer):\n",
    "            r = []   # 每个元素的行下标\n",
    "            c = []   # 每个元素的列下标\n",
    "            val = []   # 每个元素的数值\n",
    "            for i in range(layer, m - layer - 1):   # 左 \n",
    "                r.append(i)\n",
    "                c.append(layer)\n",
    "                val.append(grid[i][layer])\n",
    "            for j in range(layer, n - layer - 1):   # 下\n",
    "                r.append(m - layer - 1)\n",
    "                c.append(j)\n",
    "                val.append(grid[m-layer-1][j])\n",
    "            for i in range(m - layer - 1, layer, -1):   # 右\n",
    "                r.append(i)\n",
    "                c.append(n - layer - 1)\n",
    "                val.append(grid[i][n-layer-1])\n",
    "            for j in range(n - layer - 1, layer, -1):   # 上\n",
    "                r.append(layer)\n",
    "                c.append(j)\n",
    "                val.append(grid[layer][j])\n",
    "            total = len(val)   # 每一层的元素总数\n",
    "            kk = k % total   # 等效轮转次数\n",
    "            # 找到每个下标对应的轮转后的取值\n",
    "            for i in range(total):\n",
    "                idx = (i + total - kk) % total   # 轮转后取值对应的下标\n",
    "                grid[r[i]][c[i]] = val[idx]\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def rotate(x,y,m,n):\n",
    "            t = k % (2*m+2*n-4)\n",
    "            tmp = []\n",
    "            for i in range(x,x+m-1):\n",
    "                tmp.append(grid[i][y])\n",
    "            for j in range(y,y+n-1):\n",
    "                tmp.append(grid[x+m-1][j])\n",
    "            for i in range(x+m-1,x,-1):\n",
    "                tmp.append(grid[i][y+n-1])\n",
    "            for j in range(y+n-1,y,-1):\n",
    "                tmp.append(grid[x][j])\n",
    "            tmp = tmp[-t:] +tmp[:-t]\n",
    "            idx = 0\n",
    "            for i in range(x,x+m-1):\n",
    "                grid[i][y] = tmp[idx]\n",
    "                idx += 1\n",
    "            for j in range(y,y+n-1):\n",
    "                grid[x+m-1][j] = tmp[idx]\n",
    "                idx += 1\n",
    "            for i in range(x+m-1,x,-1):\n",
    "                grid[i][y+n-1] = tmp[idx]\n",
    "                idx += 1\n",
    "            for j in range(y+n-1,y,-1):\n",
    "                grid[x][j] = tmp[idx]\n",
    "                idx += 1\n",
    "            return\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        x,y = 0,0\n",
    "        while(m >= 2 and n >= 2):\n",
    "            rotate(x,y,m,n)\n",
    "            m -= 2\n",
    "            n -= 2\n",
    "            x += 1\n",
    "            y += 1\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid, k: int):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        nlayer = min(m // 2, n // 2)\n",
    "\n",
    "        for layer in range(nlayer):\n",
    "            r = []\n",
    "            c = []\n",
    "            val = []\n",
    "            for i in range(layer, m - layer - 1):\n",
    "                r.append(i)\n",
    "                c.append(layer)\n",
    "                val.append(grid[i][layer])\n",
    "            for j in range(layer, n - layer -1):\n",
    "                r.append(m - layer - 1)\n",
    "                c.append(j)\n",
    "                val.append(grid[m - layer -1][j])\n",
    "            for i in range(m - layer - 1, layer, -1):\n",
    "                r.append(i)\n",
    "                c.append(n - layer - 1)\n",
    "                val.append(grid[i][n - layer - 1])\n",
    "            for j in range(n - layer - 1, layer, -1):\n",
    "                r.append(layer)\n",
    "                c.append(j)\n",
    "                val.append(grid[layer][j])\n",
    "            total = len(val)\n",
    "            kk = k % total\n",
    "\n",
    "            for i in range(total):\n",
    "                idx = (i + total - kk) % total\n",
    "                grid[r[i]][c[i]] = val[idx]\n",
    "        return grid\n",
    "        #把每个值的位置和值记录下来\n",
    "        #在加上偏移量即可"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        nlayer = min(m // 2, n // 2)   # 层数\n",
    "        # 从左上角起逆时针枚举每一层\n",
    "        for layer in range(nlayer):\n",
    "            r = []   # 每个元素的行下标\n",
    "            c = []   # 每个元素的列下标\n",
    "            val = []   # 每个元素的数值\n",
    "            for i in range(layer, m - layer - 1):   # 左 \n",
    "                r.append(i)\n",
    "                c.append(layer)\n",
    "                val.append(grid[i][layer])\n",
    "            for j in range(layer, n - layer - 1):   # 下\n",
    "                r.append(m - layer - 1)\n",
    "                c.append(j)\n",
    "                val.append(grid[m-layer-1][j])\n",
    "            for i in range(m - layer - 1, layer, -1):   # 右\n",
    "                r.append(i)\n",
    "                c.append(n - layer - 1)\n",
    "                val.append(grid[i][n-layer-1])\n",
    "            for j in range(n - layer - 1, layer, -1):   # 上\n",
    "                r.append(layer)\n",
    "                c.append(j)\n",
    "                val.append(grid[layer][j])\n",
    "            total = len(val)\n",
    "            kk = k % total\n",
    "            for i in range(total):\n",
    "                idx = (i + total - kk) % total\n",
    "                grid[r[i]][c[i]] = val[idx]\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from functools import lru_cache\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        h = len(grid)\n",
    "        w = len(grid[0])\n",
    "        def get_layer(idx):\n",
    "            nonlocal h, w\n",
    "            st = (idx, idx)\n",
    "            ll = [st]\n",
    "            prev = st\n",
    "            while st[1] < (w -  idx - 1):\n",
    "                st = st[0], min(w - 1, st[1] + 1)\n",
    "                if st == prev:\n",
    "                    break\n",
    "                prev = st\n",
    "                ll.append(st)\n",
    "\n",
    "            while st[0] < (h -  idx -1 ):\n",
    "                st = min(h-1, st[0]+1), st[1]\n",
    "                if st == prev:\n",
    "                    break\n",
    "                prev = st\n",
    "                ll.append(st)\n",
    "            while st[1] > idx:\n",
    "                st = st[0], max(0, st[1] - 1)\n",
    "                if st == prev:\n",
    "                    break\n",
    "                prev = st\n",
    "                ll.append(st)\n",
    "            while st[0] > idx:\n",
    "                st = max(0,st[0] - 1), st[1]\n",
    "                if st == prev:\n",
    "                    break\n",
    "                prev = st\n",
    "                ll.append(st)\n",
    "            ll.pop()\n",
    "            return ll\n",
    "\n",
    "        def adjust_value(idx_list, pos):\n",
    "            curv = [grid[i[0]][i[1]] for i in idx_list]\n",
    "            curv = curv[pos:] + curv[:pos]\n",
    "            for i, v in zip(idx_list, curv):\n",
    "                grid[i[0]][i[1]] = v\n",
    "\n",
    "        for i in range(min(h//2, w//2)):\n",
    "            todo = get_layer(i)\n",
    "            if len(todo) == k:\n",
    "                continue\n",
    "            adjust_value(todo, k % len(todo))\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "\n",
    "        t, b = 0, m - 1\n",
    "        l, r = 0, n - 1\n",
    "        \n",
    "        while t < b and l < r:\n",
    "            dic = {}\n",
    "            res = []\n",
    "            for i in range(t, b):\n",
    "                dic[i, l] = len(res)\n",
    "                res.append((i, l, grid[i][l]))\n",
    "            for j in range(l, r):\n",
    "                dic[b, j] = len(res)\n",
    "                res.append((b, j, grid[b][j]))\n",
    "            for i in range(b, t, -1):\n",
    "                dic[i, r] = len(res)\n",
    "                res.append((i, r, grid[i][r]))\n",
    "            for j in range(r, l, -1):\n",
    "                dic[t, j] = len(res)\n",
    "                res.append((t, j, grid[t][j]))\n",
    "            \n",
    "            x = len(res)\n",
    "            for (i, j), v in dic.items():\n",
    "                idx = (v + k) % x\n",
    "                o, p = res[idx][:2]\n",
    "                ans[o][p] = grid[i][j]\n",
    "\n",
    "            t += 1\n",
    "            b -= 1\n",
    "            l += 1\n",
    "            r -= 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateCircle(self, grid, left, right, up, down, k):\n",
    "        if left == right or up == down:\n",
    "            return # just a strip\n",
    "        \n",
    "        data = []\n",
    "        idx = 0\n",
    "        \n",
    "        for i in range(left, right + 1):\n",
    "            data.append(grid[up][i]) #-->\n",
    "\n",
    "        for i in range(up + 1, down + 1):\n",
    "            data.append(grid[i][right]) # up\n",
    "\n",
    "        for i in range(right - 1, left - 1, -1):\n",
    "            data.append(grid[down][i])\n",
    "       \n",
    "        for i in range(down - 1, up, -1):\n",
    "            data.append(grid[i][left])\n",
    "        \n",
    "        rotate_amt = k % len(data)\n",
    "        data = data[rotate_amt:] + data[:rotate_amt]\n",
    "        idx = 0\n",
    "        for i in range(left, right + 1):\n",
    "            grid[up][i] = data[idx] #-->\n",
    "            idx += 1\n",
    "        for i in range(up + 1, down + 1):\n",
    "            grid[i][right] = data[idx] # up\n",
    "            idx += 1\n",
    "        for i in range(right - 1, left - 1, -1):\n",
    "            grid[down][i] = data[idx]\n",
    "            idx += 1\n",
    "       \n",
    "        for i in range(down - 1, up, -1):\n",
    "            grid[i][left] = data[idx]\n",
    "            idx += 1\n",
    "        \n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        n_row = len(grid)\n",
    "        n_col = len(grid[0])\n",
    "        n_layers = min(n_row // 2, n_col // 2)\n",
    "        \n",
    "        for layer_idx in range(n_layers):\n",
    "            left = layer_idx\n",
    "            right = n_col - 1 - layer_idx\n",
    "            up = layer_idx\n",
    "            down = n_row - 1 - layer_idx\n",
    "            self.rotateCircle(grid, left, right, up, down, k)\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        nlayer = min(m//2, n//2)\n",
    "        for layer in range(nlayer):\n",
    "            row = []\n",
    "            col = []\n",
    "            val = []\n",
    "            # left \n",
    "            for i in range(layer, m-layer-1):\n",
    "                row.append(i)\n",
    "                col.append(layer)\n",
    "                val.append(grid[i][layer])\n",
    "            # down\n",
    "            for j in range(layer, n-layer-1):\n",
    "                col.append(j)\n",
    "                row.append(m-layer-1)\n",
    "                val.append(grid[m-layer-1][j])\n",
    "            # right\n",
    "            for i in range(m-layer-1, layer, -1):\n",
    "                row.append(i)\n",
    "                col.append(n-layer-1)\n",
    "                val.append(grid[i][n-layer-1])\n",
    "            # up\n",
    "            for j in range(n-layer-1, layer, -1):\n",
    "                col.append(j)\n",
    "                row.append(layer)\n",
    "                val.append(grid[layer][j])\n",
    "                \n",
    "            total = len(val)\n",
    "            kk = k % total # 最简轮转次数\n",
    "\n",
    "            for i in range(total):\n",
    "                idx = (i+total-kk) % total  # 替换的坐标\n",
    "                grid[row[i]][col[i]] = val[idx]\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 枚举每一层\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        nlayer = min(m // 2, n // 2)   # 层数\n",
    "        # 从左上角起逆时针枚举每一层\n",
    "        for layer in range(nlayer):\n",
    "            r = []   # 每个元素的行下标\n",
    "            c = []   # 每个元素的列下标\n",
    "            val = []   # 每个元素的数值\n",
    "            for i in range(layer, m - layer - 1):   # 左 \n",
    "                r.append(i)\n",
    "                c.append(layer)\n",
    "                val.append(grid[i][layer])\n",
    "\n",
    "            for j in range(layer, n - layer - 1):   # 下\n",
    "                r.append(m - layer - 1)\n",
    "                c.append(j)\n",
    "                val.append(grid[m-layer-1][j])\n",
    "\n",
    "            for i in range(m - layer - 1, layer, -1):   # 右\n",
    "                r.append(i)\n",
    "                c.append(n - layer - 1)\n",
    "                val.append(grid[i][n-layer-1])\n",
    "\n",
    "            for j in range(n - layer - 1, layer, -1):   # 上\n",
    "                r.append(layer)\n",
    "                c.append(j)\n",
    "                val.append(grid[layer][j])\n",
    "\n",
    "            total = len(val)   # 每一层的元素总数\n",
    "            kk = k % total   # 等效轮转次数\n",
    "            # 找到每个下标对应的轮转后的取值\n",
    "            for i in range(total):\n",
    "                idx = (i + total - kk) % total   # 轮转后取值对应的下标\n",
    "                grid[r[i]][c[i]] = val[idx]\n",
    "\n",
    "        return grid\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visit = [[0] * n for _ in range(m)]\n",
    "        ind = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visit[i][j]:\n",
    "                    continue\n",
    "                visit[i][j] = 1\n",
    "                tmp = [[i, j]]\n",
    "                d = 0\n",
    "                x, y = i, j\n",
    "                while True:\n",
    "                    if not (0 <= x + ind[d][0] < m and 0 <= y + ind[d][1] < n and not visit[x + ind[d][0]][y + ind[d][1]]):\n",
    "                        d = d + 1\n",
    "                    if d > 3:\n",
    "                        break\n",
    "                    x += ind[d][0]\n",
    "                    y += ind[d][1]\n",
    "                    if x == i and y == j:\n",
    "                        break\n",
    "                    visit[x][y] = 1\n",
    "                    tmp.append([x, y])\n",
    "\n",
    "                value = [grid[x][y] for x, y in tmp]\n",
    "                for w in range(len(value)):\n",
    "                    x, y = tmp[w]\n",
    "                    grid[x][y] = value[(w + k) % len(value)]\n",
    "\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for level in range(min(m, n) >> 1):\n",
    "            lstp, lstv = zip(*[[(r, level)        , grid[r][level]        ] for r in range(level, m - level - 1)    ] + \\\n",
    "                              [[(m - level - 1, c), grid[m - level - 1][c]] for c in range(level, n - level - 1)    ] + \\\n",
    "                              [[(r, n - level - 1), grid[r][n - level - 1]] for r in range(m - level - 1, level, -1)] + \\\n",
    "                              [[(level, c)        , grid[level][c]        ] for c in range(n - level - 1, level, -1)])\n",
    "            for p, v in zip(lstp, lstv[- (k_ := k % len(lstv)):] + lstv[:- k_]): grid[p[0]][p[1]] = v\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        level = min(m,n)>>1\n",
    "        for l in range(level):\n",
    "            ii,jj,vv = zip(*[[r, l, grid[r][l]] for r in range(l, m-1-l)] + \\\n",
    "            [[m-1-l, c, grid[m-1-l][c]] for c in range(l, n-1-l)] + \\\n",
    "            [[r, n-1-l, grid[r][n-1-l]] for r in range(m-1-l, l, -1)] + \\\n",
    "            [[l, c, grid[l][c]] for c in range(n-1-l, l, -1)])\n",
    "            length = len(vv)\n",
    "            for i,j,v in zip(ii,jj,vv[-(k%length):] + vv[:-(k%length)]):\n",
    "                grid[i][j] = v \n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "from functools import lru_cache\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        h = len(grid)\n",
    "        w = len(grid[0])\n",
    "        def get_layer(idx):\n",
    "            nonlocal h, w\n",
    "            st = (idx, idx)\n",
    "            ll = [st]\n",
    "            prev = st\n",
    "            while st[1] < (w -  idx - 1):\n",
    "                st = st[0], min(w - 1, st[1] + 1)\n",
    "                if st == prev:\n",
    "                    break\n",
    "                prev = st\n",
    "                ll.append(st)\n",
    "\n",
    "            while st[0] < (h -  idx -1 ):\n",
    "                st = min(h-1, st[0]+1), st[1]\n",
    "                if st == prev:\n",
    "                    break\n",
    "                prev = st\n",
    "                ll.append(st)\n",
    "            while st[1] > idx:\n",
    "                st = st[0], max(0, st[1] - 1)\n",
    "                if st == prev:\n",
    "                    break\n",
    "                prev = st\n",
    "                ll.append(st)\n",
    "            while st[0] > idx:\n",
    "                st = max(0,st[0] - 1), st[1]\n",
    "                if st == prev:\n",
    "                    break\n",
    "                prev = st\n",
    "                ll.append(st)\n",
    "            ll.pop()\n",
    "            return ll\n",
    "\n",
    "        def adjust_value(idx_list, pos):\n",
    "            curv = [grid[i[0]][i[1]] for i in idx_list]\n",
    "            curv = curv[pos:] + curv[:pos]\n",
    "            for i, v in zip(idx_list, curv):\n",
    "                grid[i[0]][i[1]] = v\n",
    "\n",
    "        for i in range(min(h//2, w//2)):\n",
    "            todo = get_layer(i)\n",
    "            if len(todo) == k:\n",
    "                continue\n",
    "            adjust_value(todo, k % len(todo))\n",
    "\n",
    "        return grid\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.rotateGrid([[4,5,8,9,4,2,4,7,2,4],[7,1,9,6,6,1,4,5,7,7],[7,1,5,1,1,7,10,1,3,1],[7,2,2,5,2,6,6,4,7,7],[1,2,3,8,4,7,6,9,6,2],[5,10,3,4,7,2,7,5,3,10]], 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        nlayer = min(m // 2, n // 2)   # 层数\n",
    "        # 从左上角起逆时针枚举每一层\n",
    "        for layer in range(nlayer):\n",
    "            r = []   # 每个元素的行下标\n",
    "            c = []   # 每个元素的列下标\n",
    "            val = []   # 每个元素的数值\n",
    "            for i in range(layer, m - layer - 1):   # 左 \n",
    "                r.append(i)\n",
    "                c.append(layer)\n",
    "                val.append(grid[i][layer])\n",
    "            for j in range(layer, n - layer - 1):   # 下\n",
    "                r.append(m - layer - 1)\n",
    "                c.append(j)\n",
    "                val.append(grid[m-layer-1][j])\n",
    "            for i in range(m - layer - 1, layer, -1):   # 右\n",
    "                r.append(i)\n",
    "                c.append(n - layer - 1)\n",
    "                val.append(grid[i][n-layer-1])\n",
    "            for j in range(n - layer - 1, layer, -1):   # 上\n",
    "                r.append(layer)\n",
    "                c.append(j)\n",
    "                val.append(grid[layer][j])\n",
    "            total = len(val)   # 每一层的元素总数\n",
    "            kk = k % total   # 等效轮转次数\n",
    "            # 找到每个下标对应的轮转后的取值\n",
    "            for i in range(total):\n",
    "                idx = (i + total - kk) % total   # 轮转后取值对应的下标\n",
    "                grid[r[i]][c[i]] = val[idx]\n",
    "        return grid\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
